나도 아이디어는 있었는데 이미 논문에다가 구현까지 되어 있다.
가져다 쓰면 잘 동작한다. 살벌하게 빠르다. 그럴 수 밖에 없는게 자동으로 캐시 탄다.
예전에 발견해서 찜해놓고 있다가 며칠 전 부터 가져다 쓰고 있다.
기저원리는 in-place에서 해싱하듯 접근하는 것이다. 문자는 코드로 표현하고 코드는 한정적이므로 코드 자체를 주소의 오프셋으로 쓸 수 있다. 이때 여분의 비트를 상태머신을 위한 상태코드로 쓸 수 있다. 복잡하다.
문제는 모든 문자열 처리 코드가 그렇듯 바이트 단위로 동작을 하는 관계로 SIMD에 불리하다는 것이다. cuda를 이용해서 뚝딱뚝딱 해서 고성능을 달성해 본 적은 있는데 여기선 gpu 메모리의 제한이 걸린다. 이때는 avx2 같은 방식이 아니라 진짜 바이트 단위로 노가다 시킨되, SCV 물량전으로 때우는 방식이다. dma로 pci-e를 타니까 메모리 복사라는 것이 사실 잘짜면 부담이 안 되는 케이스도 있긴 한데 이래저래 골아픈 영역이다.